package kyssion.leetcode.num151_200;

import kyssion.leetcode.util.TreeNode;

import java.util.Deque;
import java.util.LinkedList;


public class code173_二叉搜索树迭代器 {

    public static void main(String[] args) {
        TreeNode treeNode = TreeNode.create(new int[]{
                7, 3, 15, -1, -1, 9, 20
        });
        BSTIterator bstIterator = new BSTIterator(treeNode);
        while (bstIterator.hasNext()) {
            System.out.println(bstIterator.next());
        }
    }

    static class BSTIterator {
        private Deque<TreeNode> treeNodeState;
        TreeNode start;

        public BSTIterator(TreeNode root) {
            treeNodeState = new LinkedList<>();
            start = root;
            addStack(root);
        }

        /**
         * @return the next smallest number
         */
        public int next() {
            TreeNode left = treeNodeState.removeLast();
            addStack(left.right);
            return left.val;
        }

        private void addStack(TreeNode root) {
            if (root != null) {
                treeNodeState.add(root);
                addStack(root.left);
            }
        }

        /**
         * @return whether we have a next smallest number
         */
        public boolean hasNext() {
            return !treeNodeState.isEmpty();
        }
    }
}
